package org.apache.commons.graph.algorithms.scc

import org.apache.commons.graph.DirectedGraph
import org.apache.commons.graph.algorithms.scc.sample.CheriyanMehlhornGabowAlgorithm
import org.apache.commons.graph.algorithms.scc.sample.KosarajuSharirAlgorithm
import org.apache.commons.graph.algorithms.scc.sample.TarjanAlgorithm

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Allows selecting the algorithm for calculating the strongly connected component.
 *
 * @param <V> the Graph vertices type.
 * @param <E> the Graph edges type.
</E></V> */
interface SccAlgorithmSelector<V, E> {
    /**
     * Applies the classical Cheriyan/Mehlhorn/Gabow's algorithm to find the strongly connected components, if exist.
     *
     * @return the input graph strongly connected component.
     */
    fun applyingCheriyanMehlhornGabow(): Set<Set<V>>

    /**
     * Applies the classical Kosaraju's algorithm to find the strongly connected components.
     *
     *
     * Note: the runtime complexity is O(V + E) and this algorithm should be chosen
     * if the number of vertices outweighs the number of edges.
     *
     * @return the input graph strongly connected components.
     */
    fun applyingKosarajuSharir(): Set<Set<V>>

    /**
     * Applies the classical Kosaraju's algorithm to find the strongly connected components of
     * a vertex `source`.
     *
     * @param source the source vertex to start the search from
     * @return the input graph strongly connected component.
     */
    fun applyingKosarajuSharir(source: V): Set<V>

    /**
     * Tarjan's algorithm is a variation (slightly faster) on KosarajuSharir's algorithm for finding
     * strongly-connected components in a directed graph.
     *
     *
     * Note: the runtime complexity is O(V + E) and this algorithm should be chosen
     * if the number of edges outweighs the number of vertices.
     *
     * @return the input graph strongly connected component.
     */
    fun applyingTarjan(): Set<Set<V>>
}


/**
 * [SccAlgorithmSelector] implementation
 *
 * @param <V> the Graph vertices type.
 * @param <E> the Graph edges type.
</E></V> */
/**
 * Create a default [SccAlgorithmSelector] for the given [org.apache.commons.graph.Graph].
 *
 * @param graph the [org.apache.commons.graph.Graph].
 */
class DefaultSccAlgorithmSelector<V, E>(
    /** The graph.  */
    private val graph: DirectedGraph<V, E>
) : SccAlgorithmSelector<V, E> {
    /**
     * Just calculates the SCC depending on the selected algorithm.
     *
     * @param algorithm
     * @return
     */
    internal fun applying(algorithm: SccAlgorithm<V>): Set<Set<V>> {
        return algorithm.perform()
    }

    /**
     * {@inheritDoc}
     */
    override fun applyingCheriyanMehlhornGabow(): Set<Set<V>> {
        return applying(CheriyanMehlhornGabowAlgorithm(graph))
    }

    /**
     * {@inheritDoc}
     */
    override fun applyingKosarajuSharir(): Set<Set<V>> {
        return applying(KosarajuSharirAlgorithm(graph))
    }

    /**
     * {@inheritDoc}
     */
    override fun applyingKosarajuSharir(source: V): Set<V> {
        return KosarajuSharirAlgorithm(graph).perform(source)
    }

    /**
     * {@inheritDoc}
     */
    override fun applyingTarjan(): Set<Set<V>> {
        return applying(TarjanAlgorithm(graph))
    }
}

fun <V, E, G : DirectedGraph<V, E>> G.findStronglyConnectedComponent(): SccAlgorithmSelector<V, E> = DefaultSccAlgorithmSelector(this)

fun <V, E, G : DirectedGraph<V, E>> G.findStronglyConnectedComponent(algorithm: SccAlgorithm<V>)
        = DefaultSccAlgorithmSelector(this).applying( algorithm = algorithm)
